Search for: All records

We demonstrate that a modification of the classical index calculus algorithm can be used to factor integers. More generally, we reduce the factoring problem to finding an overdetermined system of multiplicative relations in any factor base modulo $$n$$, where $$n$$ is the integer whose factorization is sought. The algorithm has subexponential runtime $$\exp(O(\sqrt{\log n \log \log n}))$$ (or $$\exp(O( (\log n)^{1/3} (\log \log n)^{2/3} ))$$ with the addition of a number field sieve), but requires a rational linear algebra phase, which is more intensive than the linear algebra phase of the classical index calculus algorithm. The algorithm is certainly slower than the best known factoring algorithms, but is perhaps somewhat notable for its simplicity and its similarity to the index calculus. 

Abstract In supersingular isogeny-based cryptography, the path-finding problem reduces to the endomorphism ring problem. Can path-finding be reduced to knowing just one endomorphism? It is known that a small degree endomorphism enables polynomial-time path-finding and endomorphism ring computation (in: Love and Boneh, ANTS XIV-Proceedings of the Fourteenth Algorithmic Number Theory Symposium, volume 4 of Open Book Ser. Math. Sci. Publ., Berkeley, 2020). An endomorphism gives an explicit orientation of a supersingular elliptic curve. In this paper, we use the volcano structure of the oriented supersingular isogeny graph to take ascending/descending/horizontal steps on the graph and deduce path-finding algorithms to an initial curve. Each altitude of the volcano corresponds to a unique quadratic order, called the primitive order. We introduce a new hard problem of computing the primitive order given an arbitrary endomorphism on the curve, and we also provide a sub-exponential quantum algorithm for solving it. In concurrent work (in: Wesolowski, Advances in cryptology-EUROCRYPT 2022, volume 13277 of Lecture Notes in Computer Science. Springer, Cham, 2022), it was shown that the endomorphism ring problem in the presence of one endomorphism with known primitive order reduces to a vectorization problem, implying path-finding algorithms. Our path-finding algorithms are more general in the sense that we don’t assume the knowledge of the primitive order associated with the endomorphism. 

We generalize work by Bourgain and Kontorovich [ On the local-global conjecture for integral Apollonian gaskets , Invent. Math. 196 (2014), 589–650] and Zhang [ On the local-global principle for integral Apollonian 3-circle packings , J. Reine Angew. Math. 737 , (2018), 71–110], proving an almost local-to-global property for the curvatures of certain circle packings, to a large class of Kleinian groups. Specifically, we associate in a natural way an infinite family of integral packings of circles to any Kleinian group $${\mathcal{A}}\leqslant \text{PSL}_{2}(K)$$ satisfying certain conditions, where $$K$$ is an imaginary quadratic field, and show that the curvatures of the circles in any such packing satisfy an almost local-to-global principle. A key ingredient in the proof is that $${\mathcal{A}}$$ possesses a spectral gap property, which we prove for any infinite-covolume, geometrically finite, Zariski dense Kleinian group in $$\operatorname{PSL}_{2}({\mathcal{O}}_{K})$$ containing a Zariski dense subgroup of $$\operatorname{PSL}_{2}(\mathbb{Z})$$ . 

Let ϕ(x) = xd + c be an integral polynomial of degree at least 2, and consider the sequence (ϕn(0))n=0∞, which is the orbit of 0 under iteration by ϕ. Let Dd,c denote the set of positive integers n for which n | ϕn(0). We give a characterization of Dd,c in terms of a directed graph and describe a number of its properties, including its cardinality and the primes contained therein. In particular, we study the question of which primes p have the property that the orbit of 0 is a single p-cycle modulo p. We show that the set of such primes is finite when d is even, and conjecture that it is infinite when d is odd.